Search for: All records

Abstract Kreweras words are words consisting of n $$\mathrm {A}$$ A ’s, n $$\mathrm {B}$$ B ’s, and n $$\mathrm {C}$$ C ’s in which every prefix has at least as many $$\mathrm {A}$$ A ’s as $$\mathrm {B}$$ B ’s and at least as many $$\mathrm {A}$$ A ’s as  $$\mathrm {C}$$ C ’s. Equivalently, a Kreweras word is a linear extension of the poset $$\mathsf{V}\times [n]$$ V × [ n ] . Kreweras words were introduced in 1965 by Kreweras, who gave a remarkable product formula for their enumeration. Subsequently they became a fundamental example in the theory of lattice walks in the quarter plane. We study Schützenberger’s promotion operator on the set of Kreweras words. In particular, we show that 3 n applications of promotion on a Kreweras word merely swaps the $$\mathrm {B}$$ B ’s and $$\mathrm {C}$$ C ’s. Doing so, we provide the first answer to a question of Stanley from 2009, asking for posets with ‘good’ behavior under promotion, other than the four families of shapes classified by Haiman in 1992. We also uncover a strikingly simple description of Kreweras words in terms of Kuperberg’s $$\mathfrak {sl}_3$$ sl 3 -webs, and Postnikov’s trip permutation associated with any plabic graph. In this description, Schützenberger’s promotion corresponds to rotation of the web. 

The cyclic sieving phenomenon of Reiner, Stanton, and White says that we can often count the fixed points of elements of a cyclic group acting on a combinatorial set by plugging roots of unity into a polynomial related to this set. One of the most impressive instances of the cyclic sieving phenomenon is a theorem of Rhoades asserting that the set of plane partitions in a rectangular box under the action of promotion exhibits cyclic sieving. In Rhoades's result the sieving polynomial is the size generating function for these plane partitions, which has a well-known product formula due to MacMahon. We extend Rhoades's result by also considering symmetries of plane partitions: specifically, complementation and transposition. The relevant polynomial here is the size generating function for symmetric plane partitions, whose product formula was conjectured by MacMahon and proved by Andrews and Macdonald. Finally, we explain how these symmetry results also apply to the rowmotion operator on plane partitions, which is closely related to promotion. 

Abstract For a Weyl group W of rank r , the W -Catalan number is the number of antichains of the poset of positive roots, and the W -Narayana numbers refine the W -Catalan number by keeping track of the cardinalities of these antichains. The W -Narayana numbers are symmetric – that is, the number of antichains of cardinality k is the same as the number of cardinality $r-k$ . However, this symmetry is far from obvious. Panyushev posed the problem of defining an involution on root poset antichains that exhibits the symmetry of the W -Narayana numbers. Rowmotion and rowvacuation are two related operators, defined as compositions of toggles, that give a dihedral action on the set of antichains of any ranked poset. Rowmotion acting on root posets has been the subject of a significant amount of research in the recent past. We prove that for the root posets of classical types, rowvacuation is Panyushev’s desired involution. 

We study several strengthening of classical circular security assumptions which were recently introduced in four new lattice-based constructions of indistinguishability obfuscation: Brakerski-Dottling-Garg-Malavolta (Eurocrypt 2020), Gay-Pass (STOC 2021), Brakerski-Dottling-Garg-Malavolta (Eprint 2020) and Wee-Wichs (Eprint 2020). We provide explicit counterexamples to the 2-circular shielded randomness leakage assumption w.r.t. the Gentry-Sahai-Waters fully homomorphic encryption scheme proposed by Gay-Pass, and the homomorphic pseudorandom LWE samples conjecture proposed by Wee-Wichs. Our work suggests a separation between classical circular security of the kind underlying un-levelled fully-homomorphic encryption from the strengthened versions underlying recent iO constructions, showing that they are not (yet) on the same footing. Our counterexamples exploit the flexibility to choose specific implementations of circuits, which is explicitly allowed in the Gay-Pass assumption and unspecified in the Wee-Wichs assumption. Their indistinguishabilty obfuscation schemes are still unbroken. Our work shows that the assumptions, at least, need refinement. In particular, generic leakage-resilient circular security assumptions are delicate, and their security is sensitive to the specific structure of the leakages involved. 

Propp recently introduced a variant of chip-firing on the infinite path where the chips are given distinct integer labels and conjectured that this process is confluent from certain (but not all) initial configurations of chips. Hopkins, McConville, and Propp proved Propp's confluence conjecture. We recast this result in terms of root systems: the labeled chip-firing game can be seen as a process which allows replacing an integer vector λ by λ+α whenever λ is orthogonal to α, for α a positive root of a root system of Type A. We give conjectures about confluence for this process in the general setting of an arbitrary root system. We show that the process is always confluent from any initial point after modding out by the action of the Weyl group (an analog of unlabeled chip-firing in arbitrary type). We also study some remarkable deformations of this process which are confluent from any initial point. For these deformations, the set of weights with given stabilization has an interesting geometric structure related to permutohedra. This geometric structure leads us to define certain `Ehrhart-like' polynomials that conjecturally have nonnegative integer coefficients.